Today's network links carry vast amounts of information. High bandwidth applications supported by these network links include, for example, streaming video, streaming audio, and large aggregations of voice traffic. In the future, network bandwidth demands are certain to increase.
As a business grows, so can its network, increasing in the number of network elements coupled to the network, the number of network links, and also geographic diversity. Over time, a business' network can include physical locations scattered throughout a city, a state, a country, or the world. Since it can be prohibitively expensive to create a private network that spans these great distances, many businesses opt to rely upon a third-party provider's transport network to provide connectivity between the disparate geographic sites of the business' network elements. In order for the business' network to seamlessly function through the provider network, the provider network must be able to provide a medium for transmission of all the business' various types of datastreams, including multicast transmission.
Multicast routing protocols enable multicast transmission (i.e., one-to-many connections and many-to-many connections) by replicating a multicast packet close to the destination of that packet, obviating the need for multiple unicast connections for the same purpose; thus, saving network bandwidth and improving throughput. Upon receiving a multicast packet, a network node can examine a multicast group destination address (GDA) of the packet and determine whether downstream subscribers to the multicast packet (i.e., members of the multicast group) are connected to the network node (either directly or indirectly). The network node can then replicate the multicast packet as needed and transmit the replicated packets to any connected subscribers.
FIG. 1A is a simplified block diagram of a network transporting a multicast transmission. Network router elements 110, 120, 130 and 140 are coupled through network links 150, 160, and 170. Network router element 110 is also coupled to network elements 111 and 112; network router element 120 is coupled to network element 121; network router element 130 is coupled to network elements 131 and 132; and, network router element 140 is coupled to network element 141.Such coupling between the network router elements and the network elements can be direct or indirect (e.g., via a L2 network device or another network router element).
For the purposes of this illustration, network element 111 is a multicast source transmitting to a multicast group that includes network elements 112, 121, 131, 132 and 141. A multicast datastream, having a group destination address to which the above network elements have subscribed as receiver members, is transmitted from network element 111 to network router element 110 (illustrated by the arrow from 111 to 110). Network router element 110 determines where to forward packets in the multicast datastream by referring to an internal address table that identifies each port of network router element 110 that is coupled, directly or indirectly, to a subscribing member of the multicast group. Network router element 110 then replicates packets of the multicast datastream and then transmits the packets from the identified ports to network element 112, network router element 120 and network router element 130.
Network router elements 120 and 130 can inform network router element 110 that they are coupled to a subscribing member of a multicast datastream using, for example, a protocol independent multicast (PIM) multicast message. Using PIM, network router elements 120 and 130 can send messages indicating that they need to join (a “JOIN” message) or be excluded from (a “PRUNE” message) receiving packets directed to a particular multicast group or being transmitted by a particular source. Similarly, a network element can inform a first-hop network router element that the network element wishes to be a subscriber to a multicast group by sending a membership report request through a software protocol such as internet group management protocol (IGMP). When a network element wishes to subscribe to a multicast transmission, an IGMP membership request frame can be transmitted by the network element. An IGMP-enabled network router element (or a L2 network device) can have “snooping” software executing to read such a frame and build a corresponding entry in a multicast group address table.
Upon receipt by network router elements 120 and 130, packets from the multicast datastream will be replicated as needed by those network router elements to provide the multicast datastream to network elements coupled to those network router elements (e. g. , network elements 131 and 132 or network router element 140). In this manner, a multicast datastream from network element 111 can be transmitted through a network to multiple receiving network elements. The path of such a transmission can be thought of as a tree, wherein network element 111 is the root of the tree and network elements 121, 131, 132, and 141 can be thought of as the tips of branches.
FIG. 1B is a simplified block diagram of a network in which multiple sources are transmitting to a multicast group. As in FIG. 1A, network element 111 is a source for a multicast datastream directed to a multicast group including network elements 112, 121, 131, 132, and 141. That multicast datastream is illustrated by path 180 (a solid line). Network element 132 is also transmitting a multicast datastream to the multicast group, and that datastream is illustrated by path 190 (a dashed line). In a multiple source multicast group, any subscriber network element can be a source. In order to provide this two-way routing of multicast data packets, a bidirectional version of protocol independent multicast (PIM bidir) is used to configure the network router elements in the multicast tree. In such bidirectional multicast, datastream packets are routed only along the shared bi-directional tree, which is rooted at a rendezvous point for the multicast group, rather than at a particular datastream source. Logically, a rendezvous point is an address (e. g. , a network router element) that is “upstream” from all other network elements. Passing all bi-directional multicast traffic through such a rendezvous point, establishes a loop-free tree topology with a root at the rendezvous point. In FIG. 1B, the rendezvous point is illustrated as network router element 110.
FIGS. 1A and 1B illustrate transmission of multicast datastreams in a network in which the network router elements 110, 120, 130 and 140 are directly coupled with one another. But, as stated above, as a business and its network grow, a business' network elements can become geographically diverse, and therefore the path over which the datastream must flow can include an intervening third-party provider transport network.
FIG. 2 is a simplified block diagram illustrating a network configuration in which geographically diverse subnets of a business' network are coupled through a provider transport network. The business' network includes network router elements 210, 220, 230, and 240, wherein network router element 210 is coupled to network elements 211 and 212, network router element 220 is coupled to network element 221, network router element 230 is coupled to network elements 231 and 232, and network router element 240 is coupled to network element 241. In order to connect to the providers' network, a network router element on the edge of the business' network (a customer edge router) is coupled to a network router element on the edge of the provider's network (a provider edge router). In FIG. 2, customer edge router elements 250 (1-3) are coupled to provider edge router elements 260 (1-3), respectively. Network router element 240 is coupled to provider edge router element 260 (4) (that is, network router element 240 is configured as a customer edge router).
It should be noted that the customer edge router and the provider edge router functionality can be provided by a single router. Further, a network router element such as 240 can also serve as an edge router. The provider edge routers provide access to the provider's transport network which can contain data transmission lines, network router elements, and OSI Level 2 network devices to aid in the transmission of data from one provider edge router to another provider edge router. The provider transport network illustrated in FIG. 2 contains, as an example, network router elements 270(1-5) and 270(r), which are coupled in a manner to permit transmission of packets through the transport network. Such network router elements internal to a transport network are called “core router elements” or “core routers.” A provider transport network is not limited to such a configuration, and can include any number of network router elements, transmission lines, and other L2 and L3 network devices.
In order to facilitate transmission of data through the provider transport network, the transport network can utilize different protocols from those used in coupled customer networks. Such transport network protocols can permit faster data transmission and routing through the network. Any needed translation between customer and provider transport network protocols can be performed by the edge routers.
FIG. 3A is a simplified block diagram illustrating another representation of a transport network. It should be understood that the term “transport network” corresponds to any network of coupled network router elements comprising edge network router elements and core network router elements as those terms are understood in the art. FIG. 3A illustrates a set of edge router elements PE 310, 320, 330 and 335. These edge router elements are connected by a network including core routing elements P 340 and P 350. Using transport network protocols, such as MPLS, a datastream can be transmitted from any of the edge router elements to any other edge router element via core router elements in the transport network. A datastream can also be transmitted from one of the edge router elements to a plurality of other edge router elements via a configured path through the core of the transport network; such a configured point-to-multipoint path is called a transport tree.
FIG. 3B is a simplified block diagram illustrating a transport tree configured in the transport network. Edge router PE 310 is configured as an ingress router to the transport network, while edge routers PE 320 and PE 330 are egress routers for a datastream to exit the transport network. Datastream packets can flow through the transport network core routers P 340 and P 350, which can transmit and replicate packets, as necessary. As ingress router PE 310 receives datastream packets destined for the transport tree, PE 310 can add to the packets a transport tree identifier that identifies the transport tree over which the packets should flow. Core routers P 340 and P 350 can use this transport tree identifier to locally direct datastream packets to one or more downstream nodes in the transport tree. The transport tree identifier can be included in datastream packets as a label or, in one embodiment of the present invention, in an FEC field of the packet. In a typical transport network, core routers can retain state information for a transport tree identifier (a transport tree state) that includes an identity of an upstream router element and one or more downstream router elements. Using such a transport tree state, core router elements contain only local knowledge related to a transport tree and not knowledge of each transport tree node.
FIG. 3C illustrates an association of a multicast session with the transport tree illustrated in FIG. 3B. A point-to-multipoint multicast session is typically identified by a (S, G) tuple representing a source address and a group destination address for the multicast session. Similarly, a multipoint-to-multipoint multicast session is typically identified by a (RP, G) tuple representing a rendezvous point address and a group destination address. As stated above, when a network element wishes to subscribe to a multicast transmission, the network element can transmit a JOIN session request. Such a request can include the identifying tuple of the multicast session. In FIG. 3C, subscriber nodes R1 and R2 are coupled to edge router elements PE 320 and PE 330, respectively, while a source for the multicast data stream S1 is coupled to edge router element PE 310.
Upon receiving a join request (e. g. , IGMP or PIM), an edge router element coupled to the requesting network element (an egress router element) can determine the identity of an edge router element coupled to a network including the identified source of the multicast data stream (an ingress router element). Once such an identification is made, the egress router element can notify the ingress router element that the egress router element is coupled to a requesting subscriber of the multicast session. The ingress router element can then respond to the notification of the requesting subscriber by creating a transport tree that spans the transport network from ingress to egress router elements or associating the notifying egress router element with an already existing transport tree and modifying that existing transport tree to include the egress node if necessary. Once such a transport tree decision has been made by the ingress router element, the ingress router element will provide the notifying egress router element of an association between the multicast session and the identifier of the transport tree along which the ingress router element will transmit data packets from the requested multicast datastream. In such a manner, a multicast session can be associated with a transport tree through a transport network.
FIG. 3D is a simplified block diagram illustrating multicast flooding on a transport tree through a transport network. In FIG. 3D, two different multicast sessions share the same transport tree, wherein the transport tree is the same as that described for FIG. 3C. Multicast session SI is received by ingress router PE 310 and provided to egress routers PE 320 and PE 330 through the transport network core. Network elements R1 and R2 subscribe to session S1. Multicast session S2 is likewise transmitted through the transport tree and is received by subscribers R3 and R4 coupled to PE 320 and PE 330, respectively. Should network element R2 opt to no longer subscribe to multicast session S1, edge router PE 330 will no longer have a subscriber to multicast session S1. If PE 330 continues to receive datastream packets for multicast session S1, then PE 330 will drop those packets. Such receiving of unnecessary packets results in wasted bandwidth on the core network and overhead processing by PE 330to analyze and drop unnecessary packets. Such a state in which edge routers that are members of a transport tree are receiving multicast datastream packets for which the edge routers do not have a corresponding subscriber node is called “flooding. ” Due to this consumption of network resources, flooding is an undesirable situation.
An obvious way to avoid flooding is to have a one-to-one correlation between multicast sessions and transport trees. Therefore, each multicast session would have its own transport tree and the selection of egress routing elements would always correspond to the multicast session. A drawback of this approach is that the number of transport trees can grow linearly with the number of multicast sessions. Since each edge and core router element in a transport network retains state information related to the transport trees transiting that router element, scalability problems can result in the transport network. Such scalability problems include costs related to maintaining label and state space in the router elements, where those costs include memory, processing cycles expended during table lookups, and administration of the network. Such scalability issues are avoided, at least in part, by having multicast sessions share transport trees where appropriate.
It is therefore desirable to have a method by which to dynamically map a multicast session to a transport tree in order to avoid persistent flooding of egress routers and minimizes the amount of transient flooding during the dynamic mapping, while at the same time avoiding interruption of multicast session datastream packets for established sessions.